package com.cat.chapter038;

import java.util.Map;
import java.util.Stack;

/**
 * @author cat
 * @description
 * @create 2025/7/8 14:11
 * @since JDK17
 */

public class Solution07 {
    static Stack<Integer> stack = new Stack<>();

    public static int deep() {
        if (stack.isEmpty()) {
            return 0;
        }

        Integer ans = stack.pop();
        int d = deep() + 1;
        stack.push(ans);
        return d;
    }

    public static int max(int deep) {
        if (deep == 0) {
            return Integer.MIN_VALUE;
        }
        int cur = stack.pop();
        int ans = Math.max(cur, max(deep - 1));
        stack.push(cur);
        return ans;
    }

    public static int times(int deep, int max) {
        if (deep == 0) {    // 栈空了
            return 0;
        }

        int num = stack.pop();
        int count = (num == max ? 1 : 0) + times(deep - 1, max);
        stack.push(num);
        return count;
    }

    public static void down(int deep, int max, int times) {
        if (deep == 0) {
            for (int i = 0; i < times; i++) {
                stack.push(max);
            }
        } else {
            int num = stack.pop();
            down(deep - 1, max, times);
            if (num != max) {
                stack.push(num);
            }
        }
    }

    public static void sort() {
        int deep = deep();
        while (deep > 0) {
            int max = max(deep);
            int times = times(deep, max);
            down(deep, max, times);
            deep -= times;
        }
    }

    public static void main(String[] args) {
        stack.push(3);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        stack.push(6);
        stack.push(6);
        stack.push(4);
        stack.push(6);

        System.out.println("deep() = " + deep());
        System.out.println("max(deep()) = " + max(deep()));
        System.out.println("times(deep(), max(deep())) = " + times(deep(), max(deep())));
        down(deep(), max(deep()), times(deep(), max(deep())));
        sort();

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }

    }
}
